package basic.study.algorithms.solution.Stringmatching.single;

/**
 * @author Kevin
 * @date 2020/2/15 17:58
 */
public class BM {
    private static final int SIZE = 256; // 全局变量或成员变量
     private static void generateBC(char[] b, int m, int[] bc){
        for (int i = 0; i < SIZE; ++i) {
            bc[i] = -1; // 初始化bc
        }
        for (int i = 0; i < m; ++i) {
            int ascii = (int)b[i]; // 计算b[i]的ASCII值
            bc[ascii] = i;
        }
     }

    // b表示模式串，m表示长度，suffix，prefix数组事先申请好了
    private static void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; ++i) { // 初始化
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m - 1; ++i) { // b[0, i]
            int j = i;
            int k = 0; // 公共后缀子串长度
            while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
                --j;
                ++k;
                suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
            }
            if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
        }
    }
    // a,b表示主串和模式串；n，m表示主串和模式串的长度
    public static int bm(char[] a, int n, char[] b, int m) {
        int[] bc = new int[SIZE];// 记录模式串中每个字符最后出现的位置
        generateBC(b, m, bc);// 构建坏字符哈希表
        // 预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置
        int[] suffix = new int[m];// suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值
        boolean[] prefix = new boolean[m];//来记录模式串的后缀子串是否能匹配模式串的前缀子串,公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true
        generateGS(b, m, suffix, prefix);
        int i = 0;
        while( i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
                if(a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
            }
            if (j < 0) {
                return i; //匹配成功，返回主串与模式第一个匹配的字符的位置
            }
            int x = j - bc[(int)a[i+j]];//坏字符的模式串偏移位数
            int y = 0;// 好后缀的模式串偏移位数
            if (j < m - 1) { //如果有好后缀的话
                y = moveByGS(j, m, suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    // 在模式串跟主串匹配的过程中，遇到不能匹配的字符时，根据好后缀规则，计算模式串往后滑动的位数
    // j表示坏字符对应的模式串中的字符下标; m表示模式串长度
    private static int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - 1 - j; // 好后缀长度
        //如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），就是如果存在完整的好后缀，那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段
        if (suffix[k] != -1) return j - suffix[k] +1;
        for (int r = j+2; r <= m-1; ++r) {
            //好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。
            if (prefix[m-r] == true) {
                return r;
            }
        }
        return m;
    }

}
